'''
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
如果是，返回 true ；否则，返回 false 。
'''

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if head is None:
            return head
        
        '''
            快慢指针
        '''
        
        def reverse(head):
            #递归终止条件
            if not head or not head.next:
                return head
            last = reverse(head.next)
            head.next.next = head
            head.next = None
            return last
        def reverse2(head):
            t,cur = None,head
            while cur:
                next = cur.next
                cur.next = t
                t = cur
                cur = next
            return t


        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        if fast:
            slow = slow.next
        
        left,right = head,reverse2(slow)
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True
    
    '''
        利用二叉树遍历的思想
    '''
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        global left
        left = head
        def traverse(head):
            global left
            if head is None:
                return True
            res = traverse(head.next)
            #后序遍历
            if left.val != head.val:
                return False
            res = res and (head.val == left.val)
            left = left.next
            return res
            
        res = traverse(head)
        return res
            

   
        
            
